{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Score of a Path Between Two Cities"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个城市间路径的最小分数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数&nbsp;<code>n</code>&nbsp;，表示总共有&nbsp;<code>n</code>&nbsp;个城市，城市从&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;编号。给你一个二维数组&nbsp;<code>roads</code>&nbsp;，其中&nbsp;<code>roads[i] = [a<sub>i</sub>, b<sub>i</sub>, distance<sub>i</sub>]</code>&nbsp;表示城市&nbsp;<code>a<sub>i</sub></code> 和&nbsp;<code>b<sub>i</sub></code>&nbsp;之间有一条 <strong>双向</strong>&nbsp;道路，道路距离为&nbsp;<code>distance<sub>i</sub></code>&nbsp;。城市构成的图不一定是连通的。</p>\n",
    "\n",
    "<p>两个城市之间一条路径的 <strong>分数</strong>&nbsp;定义为这条路径中道路的 <strong>最小</strong>&nbsp;距离。</p>\n",
    "\n",
    "<p><span class=\"text-only\" data-eleid=\"20\" style=\"white-space: pre;\">城市</span><span class=\"text-only text-font-italic\" data-eleid=\"21\" style=\"white-space: pre;\"> </span><code><span class=\"text-only\" data-eleid=\"22\" style=\"white-space: pre;\">1</span></code><span class=\"text-only text-font-italic\" data-eleid=\"23\" style=\"white-space: pre;\"> </span><span class=\"text-only\" data-eleid=\"24\" style=\"white-space: pre;\">和城市</span><span class=\"text-only text-font-italic\" data-eleid=\"25\" style=\"white-space: pre;\"> </span><span class=\"text-only\" data-eleid=\"26\" style=\"white-space: pre;\"><code>n</code> 之间的所有路径的 </span><strong><span class=\"text-only\" data-eleid=\"27\" style=\"white-space: pre;\">最小</span></strong><span class=\"text-only\" data-eleid=\"28\" style=\"white-space: pre;\"> 分数。</span></p>\n",
    "\n",
    "<p><b>注意：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>一条路径指的是两个城市之间的道路序列。</li>\n",
    "\t<li>一条路径可以 <strong>多次</strong> 包含同一条道路，你也可以沿着路径多次到达城市 <code>1</code>&nbsp;和城市 <code>n</code>&nbsp;。</li>\n",
    "\t<li>测试数据保证城市 <code>1</code>&nbsp;和城市<code>n</code>&nbsp;之间 <strong>至少</strong>&nbsp;有一条路径。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/12/graph11.png\" style=\"width: 190px; height: 231px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>城市 1 到城市 4 的路径中，分数最小的一条为：1 -&gt; 2 -&gt; 4 。这条路径的分数是 min(9,5) = 5 。\n",
    "不存在分数更小的路径。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/10/12/graph22.png\" style=\"width: 190px; height: 231px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>城市 1 到城市 4 分数最小的路径是：1 -&gt; 2 -&gt; 1 -&gt; 3 -&gt; 4 。这条路径的分数是 min(2,2,4,7) = 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= roads.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>roads[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li><code>1 &lt;= distance<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>不会有重复的边。</li>\n",
    "\t<li>城市 <code>1</code>&nbsp;和城市 <code>n</code>&nbsp;之间至少有一条路径。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-score-of-a-path-between-two-cities](https://leetcode.cn/problems/minimum-score-of-a-path-between-two-cities/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-score-of-a-path-between-two-cities](https://leetcode.cn/problems/minimum-score-of-a-path-between-two-cities/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[1,2,9],[2,3,6],[2,4,5],[1,4,7]]', '4\\n[[1,2,2],[1,3,4],[3,4,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    roads is a list of edges with distances\n",
    "    1. city 1 and city n should in the same group\n",
    "    2. if they are in the same group, then return the smallest distance in the group\n",
    "    3. only calculate the min distance within the group of city 1 and city n, to reduce time complexity \n",
    "\n",
    "    '''\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        id = [i for i in range(n)]\n",
    "        min_dis = float(inf) \n",
    "\n",
    "        for edge in roads:\n",
    "            p = self.find_root(id, edge[0] - 1)\n",
    "            q = self.find_root(id, edge[1] - 1)\n",
    "            id[q] = p\n",
    "\n",
    "        for edge in roads:\n",
    "            if self.find_root(id, edge[0] - 1) == self.find_root(id, 0) and edge[2] < min_dis:\n",
    "                min_dis = edge[2]\n",
    "\n",
    "\n",
    "        return min_dis\n",
    "            \n",
    "\n",
    "    def find_root(self, id, i):\n",
    "        while i != id[i]:\n",
    "            id[i] = id[id[i]]\n",
    "            i = id[i]\n",
    "        return i "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        djs = list(range(n+1))\n",
    "        path = [math.inf] * (n+1)\n",
    "        def find(x:int)->int:\n",
    "            if djs[x] != x:\n",
    "                djs[x] = find(djs[x])\n",
    "            return djs[x]\n",
    "        def union(x:int,y:int,val:int)->None:\n",
    "            path[find(y)] = min(val, path[find(x)], path[find(y)])\n",
    "            djs[find(x)] = find(y)\n",
    "\n",
    "        for x , y, val in roads:\n",
    "            union(x,y,val)\n",
    "\n",
    "\n",
    "\n",
    "        return path[find(1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        fa = list(range(n+1))\n",
    "        rank = [ inf for _ in range(n+1)]\n",
    "        def find(i):\n",
    "            if fa[i] != i:\n",
    "                fa[i] = find(fa[i])\n",
    "            return fa[i]\n",
    "        def merge(i,j,v):\n",
    "            ri,rj = find(i),find(j)\n",
    "            if rj < ri:\n",
    "                ri,rj = rj,ri\n",
    "            fa[rj] = ri\n",
    "            rank[ri] = min(rank[ri],rank[rj],v)\n",
    "        for i,j,k in roads:\n",
    "            merge(i,j,k)\n",
    "        return rank[find(1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n: int):\n",
    "        # 连通分量个数\n",
    "        self.count = n\n",
    "        # 存储一棵树\n",
    "        self.parent = [x for x in range(n)]\n",
    "        # 记录树的“重量”\n",
    "        self.size = [1] * n\n",
    "    \n",
    "    def union(self, p, q):\n",
    "        rootP = self._find(p);\n",
    "        rootQ = self._find(q);\n",
    "        if rootP == rootQ:\n",
    "            return\n",
    "        \n",
    "        # 小树接到大树下面，较平衡\n",
    "        if self.size[rootP] > self.size[rootQ]:\n",
    "            self.parent[rootQ] = rootP\n",
    "            self.size[rootP] += self.size[rootQ]\n",
    "        else:\n",
    "            self.parent[rootP] = rootQ\n",
    "            self.size[rootQ] += self.size[rootP]\n",
    "        self.count -= 1\n",
    "\n",
    "    def connected(self, p, q):\n",
    "        return self._find(p) == self._find(q)\n",
    "\n",
    "    def _find(self, x):\n",
    "        while self.parent[x] != x:\n",
    "            # 进行路径压缩\n",
    "            self.parent[x] = self.parent[self.parent[x]]\n",
    "            x = self.parent[x]\n",
    "        return x\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        uf = UF(n+1)\n",
    "        # 记录城市i的最小邻边\n",
    "        adj = defaultdict(lambda: float('inf'))\n",
    "\n",
    "        for v, w, dis in roads:\n",
    "            adj[v] = min(adj[v], dis)\n",
    "            adj[w] = min(adj[w], dis)\n",
    "            uf.union(v, w)\n",
    "        \n",
    "        return min(adj[i] for i in range(1, n+1) if uf.connected(1, i)) if uf.connected(1, n) else -1\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        res = float('inf')\n",
    "        uf = UnionFind(n + 1)\n",
    "        for x, y, z in roads:\n",
    "            uf.union(x, y)\n",
    "        for x, y, z in roads:\n",
    "            if uf.is_connected(x, 1):\n",
    "                res = min(res, z)\n",
    "        return res\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.father = [i for i in range(n + 1)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.father[x] != x:\n",
    "            self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if x < y:\n",
    "            self.father[y] = x\n",
    "        else:\n",
    "            self.father[x] = y\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "#         graph = collections.defaultdict(list)\n",
    "#         for u, v, d in roads:\n",
    "#             graph[u].append([d, v])\n",
    "#             graph[v].append([d, u])\n",
    "#         self.res = float('inf')\n",
    "#         visit = set()  # 用一个集合保存已经遍历过的节点，防止陷入无限循环\n",
    "#         # 看到示例2的路径，觉得节点可以走回头路这个搜索还是挺麻烦的\n",
    "#         # 但实际上只需要找到与节点1连通的所有的边中最小值即可\n",
    "#         def dfs(i):\n",
    "#             # 递归结束的条件\n",
    "#             if i in visit:\n",
    "#                 return\n",
    "#             visit.add(i) # 添加当前节点，表示已经访问过了\n",
    "#             for d, nei in graph[i]:\n",
    "#                 self.res = min(self.res, d) # 就当前节点而言，遍历它的邻居，并更新最小值\n",
    "#                 dfs(nei) # 让邻居递归，相信邻居能继续继续更新self.res\n",
    "#         dfs(1)\n",
    "#         return self.res\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        root = [i for i in range(n+1)]\n",
    "\n",
    "        def find(a):\n",
    "            if root[a] == a:\n",
    "                return a\n",
    "            root[a] = find(root[a]) # path compression  \n",
    "            return root[a]\n",
    "\n",
    "        def union(a, b):\n",
    "            a = find(a)\n",
    "            b = find(b)\n",
    "            root[a] = b\n",
    "\n",
    "        for a, b, _ in roads:\n",
    "            union(a,b)\n",
    "\n",
    "        return min(d for a,b,d in roads if find(n) == find(a))\n",
    " \n",
    "        \n",
    "\"\"\"\n",
    "wing notes:\n",
    "It is allowed for a path to contain the same road multiple times, and you can visit cities 1 and n multiple times along the path.\n",
    "so it's not a min path problem, it's to find the min path that connects both 1 and n\n",
    "2 solutions:\n",
    "bfs or dfs (https://leetcode.cn/problems/minimum-score-of-a-path-between-two-cities/solutions/2006263/di-gui-by-aurorarocks-crtm/)\n",
    "or union find\n",
    "并查集的思路即可(相当于求包含1和n的连通分量中最短的边)，需要注意的是：由于路径可以重复所以合并的时候不需要考虑他们的parent是否相同只要有边即可合并\n",
    "\"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        s = [i for i in range(n + 1)]\n",
    "        def find(x):\n",
    "            if x != s[x]:\n",
    "                s[x] = find(s[x])\n",
    "            return s[x]\n",
    "\n",
    "        for x, y, _ in roads:\n",
    "            s[find(x)] = find(y)\n",
    "        for i in range(1, n + 1):\n",
    "            find(i)\n",
    "        return min(w for x, y, w in roads if s[x] == s[1])\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        inf = 9999999\n",
    "        next_list = [[] for _ in range(n + 1)]\n",
    "        node_score = [inf] * (n + 1)\n",
    "        for road in roads:\n",
    "            next_list[road[0]].append(road[1])\n",
    "            next_list[road[1]].append(road[0])\n",
    "            node_score[road[0]] = min(node_score[road[0]], road[2])\n",
    "            node_score[road[1]] = min(node_score[road[1]], road[2])\n",
    "        min_score = inf\n",
    "        visited = [False] * (n + 1)\n",
    "        queue = [1]\n",
    "        visited[1] = True\n",
    "        index = 0\n",
    "        while index != len(queue):\n",
    "            length = len(queue)\n",
    "            for i in range(index, length):\n",
    "                for nxt in next_list[queue[i]]:\n",
    "                    if not visited[nxt]:\n",
    "                        visited[nxt] = True\n",
    "                        queue.append(nxt)\n",
    "                        min_score = min(min_score, node_score[nxt])\n",
    "            index = length\n",
    "        return min_score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        neighbours = [[] for _ in range(n+1)]\n",
    "        for a, b, dist in roads:\n",
    "            neighbours[a].append(b)\n",
    "            neighbours[b].append(a)\n",
    "        visited = [0] * (n+1)\n",
    "        dq = deque()\n",
    "        dq.append(1)\n",
    "        visited[1] = 1\n",
    "        while dq:\n",
    "            cur = dq.popleft()\n",
    "            for ne in neighbours[cur]:\n",
    "                if visited[ne]:\n",
    "                    continue\n",
    "                visited[ne] = 1\n",
    "                dq.append(ne)\n",
    "        res = 10**5\n",
    "        for a, b, dist in roads:\n",
    "            if visited[a] or visited[b]:\n",
    "                res = min(res, dist)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        x = [[] for i in range(n + 1)]\n",
    "        y = [float('inf')] * (n + 1)\n",
    "        for i, j, k in roads:\n",
    "            x[i].append(j)\n",
    "            x[j].append(i)\n",
    "            y[i] = min(y[i], k)\n",
    "            y[j] = min(y[j], k)\n",
    "        vis = [False] * (n + 1)\n",
    "\n",
    "        ans = float('inf')\n",
    "        queue = deque([1])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            vis[node] = True\n",
    "            for i in x[node]:\n",
    "                if vis[i] == False:\n",
    "                    queue.append(i)\n",
    "                    ans = min(ans, y[i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # 每个节点最小边\n",
    "        dis = [10**5] * (n + 1)\n",
    "        for item in roads:\n",
    "            dis[item[0]] = min(dis[item[0]], item[2])\n",
    "            dis[item[1]] = min(dis[item[1]], item[2])\n",
    "\n",
    "        # 每个节点邻居\n",
    "        neighbor = defaultdict(list)\n",
    "        for item in roads:\n",
    "            neighbor[item[0]].append(item[1])\n",
    "            neighbor[item[1]].append(item[0])\n",
    "        # 广度优先遍历找所有连通节点\n",
    "        stack = [1]\n",
    "        nodeset = set()\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node in nodeset:\n",
    "                continue\n",
    "            nodeset.add(node)\n",
    "            for item in neighbor[node]:\n",
    "                stack.append(item)\n",
    "        return min([dis[i] for i in nodeset])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = collections.defaultdict(list)\n",
    "        for x, y, _ in roads:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        vis = set()\n",
    "        q = [1]\n",
    "        while q:\n",
    "            new = []\n",
    "            for x in q:\n",
    "                for y in g[x]:\n",
    "                    if y not in vis:\n",
    "                        new.append(y)\n",
    "                        vis.add(y)\n",
    "            q = new\n",
    "        ans = math.inf\n",
    "        for x, y, w in roads:\n",
    "            if x in vis and y in vis:\n",
    "                ans = min(ans, w)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        def dfs(n):\n",
    "            for i in tran[n - 1]:\n",
    "                if i not in vis:\n",
    "                    vis.add(i)\n",
    "                    dfs(i)\n",
    "\n",
    "        tran = []\n",
    "        for i in range(n):\n",
    "            tran.append([])\n",
    "        for i in range(len(roads)):\n",
    "            tran[roads[i][0] - 1].append(roads[i][1])\n",
    "            tran[roads[i][1] - 1].append(roads[i][0])\n",
    "        ans = float(\"inf\")\n",
    "        vis = set()\n",
    "        dfs(n)\n",
    "        for i in range(len(roads)):\n",
    "            if roads[i][0] in vis or roads[i][1] in vis:\n",
    "                ans = min(ans,roads[i][2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        x = [[float('inf'), 0] for i in range(n + 1)]\n",
    "        for i, j, k in roads:\n",
    "            x[i].append(j)\n",
    "            x[j].append(i)\n",
    "            x[i][0] = min(x[i][0], k)\n",
    "            x[j][0] = min(x[j][0], k)\n",
    "\n",
    "        ans = float('inf')\n",
    "        queue = deque([1])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            x[node][1] = 1\n",
    "            for idx, i in enumerate(x[node]):\n",
    "                if idx in (0, 1): continue\n",
    "                if x[i][1] == 0:\n",
    "                    queue.append(i)\n",
    "                    ans = min(ans, x[i][0])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        pa = {i:i for i in range(1,n+1)}\n",
    "        minpath = {i:10**5 for i in range(1,n+1)}\n",
    "        def find(x):\n",
    "            if pa[x]!=x:\n",
    "                pa[x] = find(pa[x])\n",
    "            return pa[x]\n",
    "        def union(x,y,v):\n",
    "            pax = find(x)\n",
    "            pay = find(y)\n",
    "            if pax==pay:\n",
    "                minpath[pax] = min(minpath[pax],v)\n",
    "            else:\n",
    "                pa[pay] = pax\n",
    "                minpath[pax] = min(minpath[pax],v,minpath[pay])\n",
    "        for x,y,v in roads:\n",
    "            union(x,y,v)\n",
    "        root = find(1)\n",
    "        return minpath[root]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        res=inf\n",
    "        used=[False]*n\n",
    "        q=deque([1])\n",
    "        adjs=[[] for i in range(n+1)]\n",
    "        for a,b,d in roads:\n",
    "            adjs[a].append((b,d))\n",
    "            adjs[b].append((a,d))\n",
    "        while q:\n",
    "            for nxt,d in adjs[q.popleft()]:\n",
    "                if d<res: res=d\n",
    "                if used[nxt-1]:continue\n",
    "                used[nxt-1]=True\n",
    "                q.append(nxt)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ans = 10 ** 4 + 1\n",
    "        cities = [[] for _ in range(n + 1)]\n",
    "        for road in roads:\n",
    "            from_city, to_city, weight = road\n",
    "            cities[from_city].append((to_city, weight))\n",
    "            cities[to_city].append((from_city, weight))\n",
    "        # visited = [False] * (n + 1)\n",
    "        stack = [1]\n",
    "        #dfs\n",
    "        while len(stack) > 0:\n",
    "            city = stack.pop(-1)\n",
    "            # visited[city] = True\n",
    "            to_cities = cities[city]\n",
    "            if len(to_cities) > 0:\n",
    "                to_city, weight = to_cities.pop(-1)\n",
    "                stack.append(city)\n",
    "                stack.append(to_city)\n",
    "                ans = min(ans, weight)\n",
    "            \n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet(object):\n",
    "    def __init__(self, data_list):\n",
    "        self.parent = {}\t\t\t   \n",
    "        self.rank = {}\t\t\t\t\n",
    "        self.path = {}   \n",
    "        self.sets_count=len(data_list) # 判断并查集里共有几个集合, 初始化默认互相独立\n",
    "\n",
    "        for d in data_list:\n",
    "            self.parent[d] = d\t\t   # 初始化节点的父节点为自身\n",
    "            self.rank[d] = 1\t\t   # 初始化rank为1\n",
    "            self.path[d] = 10000000\n",
    "    def find(self, d):\n",
    "        father = self.parent[d]\n",
    "        if(d != father):\n",
    "            father = self.find(father)\n",
    "        self.parent[d] = father\n",
    "        return father\n",
    "\n",
    "    def is_same_set(self, a,b):\n",
    "        return self.find(a) == self.find(b)\n",
    "\n",
    "    def union(self, a, b, cost):\n",
    "        \"\"\"将两个集合合并在一起\"\"\"\n",
    "        if not a or not b:return\n",
    "\n",
    "        a_head = self.find(a)\n",
    "        b_head = self.find(b)\n",
    "\n",
    "        if(a_head != b_head):\n",
    "            a_rank = self.rank[a_head]\n",
    "            b_rank = self.rank[b_head]\n",
    "            if a_rank >= b_rank:\n",
    "                self.parent[b_head] = a_head\n",
    "                if a_rank==b_rank:\n",
    "                    self.rank[a_rank]+=1\n",
    "            else:\n",
    "                self.parent[a_head] = b_head\n",
    "                \n",
    "            self.sets_count-=1\n",
    "        self.path[a_head] = min(self.path[a_head],self.path[b_head],cost)\n",
    "        self.path[b_head] = min(self.path[a_head],self.path[b_head],cost)\n",
    "\n",
    "\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        a = list(range(n+1)[1:])\n",
    "        ufs = UnionFindSet(a)\n",
    "\n",
    "        for i,j,k in roads:\n",
    "            ufs.union(i,j,k)\n",
    "        #print(ufs.is_same_set(1,35))\n",
    "        print(ufs.parent)\n",
    "        return ufs.path[ufs.parent[1]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def cup(self, m, s, n):\n",
    "        if n in s:\n",
    "            return s\n",
    "        else:\n",
    "            s.add(n)\n",
    "            for i in m[n]:\n",
    "                s = self.cup(m ,s, i)\n",
    "        return s\n",
    "    def minScore(self, n: int, roads: List[List[int]]):\n",
    "        z = dict()\n",
    "        ans = 10000\n",
    "        for i in roads:\n",
    "            if i[0] in z:\n",
    "                z[i[0]].append(i[1])\n",
    "            else:\n",
    "                z[i[0]] = [i[1]]\n",
    "            if i[1] in z:\n",
    "                z[i[1]].append(i[0])\n",
    "            else:\n",
    "                z[i[1]] = [i[0]]\n",
    "        s = set()\n",
    "        s = self.cup(z, s, 1)\n",
    "        for i in roads:\n",
    "            if i[0] in s:\n",
    "                ans = min(ans, i[2])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0]*n\n",
    "    \n",
    "    def find(self,i):\n",
    "        if self.parent[i]!=i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "    \n",
    "    def union(self,x,y):\n",
    "        rootx = self.find(x)\n",
    "        rooty = self.find(y)\n",
    "        if rootx!=rooty:\n",
    "            if self.rank[rootx]<self.rank[rooty]:\n",
    "                rootx,rooty = rooty,rootx\n",
    "            self.parent[rooty] = rootx\n",
    "            if self.rank[rootx] == self.rank[rooty]:\n",
    "                self.rank[rootx] += 1\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        uf = UnionFind(n)\n",
    "        g = defaultdict(list)\n",
    "        for a, b, d in roads:\n",
    "            g[a-1].append(d)\n",
    "            g[b-1].append(d)\n",
    "            uf.union(a-1, b-1)\n",
    "        root = uf.find(0)\n",
    "        return min(min(g[i]) for i in range(n) if uf.find(i) == root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        nei = [[] for _ in range(n+1)]\n",
    "        for f, t, v in roads:\n",
    "            nei[f].append(t)\n",
    "            nei[t].append(f)\n",
    "        def bfs(root):\n",
    "            q = collections.deque([root])\n",
    "            visited = set()\n",
    "            res = set()\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                for nxt in nei[cur]:\n",
    "                    if nxt not in visited:\n",
    "                        res.add(nxt)\n",
    "                        visited.add(nxt)\n",
    "                        q.append(nxt)\n",
    "            return res\n",
    "        ff = bfs(1)\n",
    "        tt = bfs(n)\n",
    "        roads = sorted(roads, key = lambda x: x[2])\n",
    "        for f, t, v in roads:\n",
    "            if f in ff and t in tt:\n",
    "                return v\n",
    "        return -1\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "\n",
    "        g = defaultdict(list) \n",
    "        for a,b,c in roads:\n",
    "            g[a].append(b)  \n",
    "            g[b].append(a)  \n",
    "\n",
    "        visited = set()  \n",
    "\n",
    "        # 测试数据保证城市 1 和城市n 之间 至少 有一条路径。 \n",
    "        # 一条路径可以 多次 包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 。\n",
    "        def dfs(x):\n",
    "            visited.add(x)\n",
    "            for item in g[x]:\n",
    "                if item not in visited:\n",
    "                    dfs(item)\n",
    "\n",
    "        dfs(1) \n",
    "        save = list()  \n",
    "\n",
    "        for item in roads:\n",
    "            # if item[0] in visited or item[1] in visited:\n",
    "            if item[0] in visited:\n",
    "                save.append(item[2])  \n",
    "\n",
    "        return min(save)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        \n",
    "        adj = defaultdict(list)\n",
    "        for u,v,dist in roads:\n",
    "            adj[u].append((v,dist))\n",
    "            adj[v].append((u,dist))\n",
    "        \n",
    "        res = float('inf')\n",
    "        visited = [0]*(n+1)\n",
    "        queue = collections.deque()\n",
    "        queue.append(1)\n",
    "        visited[1] = 1\n",
    "        while queue:\n",
    "            t = queue.popleft()\n",
    "            for v,d in adj[t]:\n",
    "                res = min(res,d)\n",
    "        \n",
    "                if visited[v]:\n",
    "                    continue\n",
    "                queue.append(v)\n",
    "                visited[v]=1\n",
    "                \n",
    "        # def dfs(u):\n",
    "        #     nonlocal res\n",
    "        #     visited[u]=1\n",
    "        #     for v,d in adj[u]:\n",
    "        #         if not visited[v]:\n",
    "        #             if res<=d:\n",
    "        #                 break\n",
    "        #             else:\n",
    "        #                 res = d\n",
    "        #                 dfs(v)\n",
    "        #     visited[u]=0\n",
    "        # for v,d in adj[1]:\n",
    "        #     dfs(v)\n",
    "        # dfs(1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "\n",
    "        # for i,ele in enumerate(roads):\n",
    "        #     if ele[0]>ele[1]:\n",
    "        #         roads[i]=[ele[1],ele[0],ele[2]]\n",
    "\n",
    "        # my_dict1=collections.defaultdict(list)\n",
    "        # my_dict2=collections.defaultdict(list)\n",
    "\n",
    "        # for i in roads:\n",
    "        #     if i[0]<i[1]:\n",
    "        #         my_dict1[i[0]].append(i[1])\n",
    "        #         my_dict2[i[0]].append(i[2])\n",
    "        #     else:\n",
    "        #         my_dict1[i[1]].append(i[0])\n",
    "        #         my_dict2[i[1]].append(i[2])\n",
    "\n",
    "        # now_list=my_dict1[1]\n",
    "        # result=min(my_dict2[1])\n",
    "\n",
    "        # while now_list:\n",
    "        #     now_list=list(set(now_list))\n",
    "        #     next_list=[]\n",
    "        #     for j in now_list:\n",
    "        #         next_list=next_list+my_dict1[j]\n",
    "        #         if j in my_dict2:\n",
    "        #             result=min(result,min(my_dict2[j]))\n",
    "        #     now_list=next_list.copy()\n",
    "        \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # my_mat=[i for i in range(n+1)]\n",
    "\n",
    "        # def find(x):\n",
    "        #     if my_mat[x]==x:\n",
    "        #         return x\n",
    "        #     else:\n",
    "        #         return find(my_mat[x])\n",
    "\n",
    "        # def union(x,y):\n",
    "        #     my_mat[find(x)]=find(y)\n",
    "\n",
    "\n",
    "        # for i in roads:\n",
    "        #     union(i[0],i[1])\n",
    "\n",
    "        # result=10**4\n",
    "        # for i in roads:\n",
    "        #     if find(i[0])==find(1):\n",
    "        #         result=min(result,i[2])\n",
    "        \n",
    "\n",
    "\n",
    "        my_dict=collections.defaultdict(list)\n",
    "        for i in roads:\n",
    "            my_dict[i[0]].append(i[1])\n",
    "            my_dict[i[1]].append(i[0])\n",
    "\n",
    "        \n",
    "\n",
    "        # now_list1=my_dict[1]\n",
    "        # search_dict=collections.defaultdict(int)\n",
    "        # search_dict[1]+=1\n",
    "        now_list1=[1]\n",
    "        search_dict=collections.defaultdict(int)\n",
    "        search_dict[1]+=1\n",
    "\n",
    "        while now_list1:\n",
    "            # now_list1=list(set(now_list1))\n",
    "            next_list=[]\n",
    "            for j in now_list1:\n",
    "                for k in my_dict[j]:\n",
    "                    if k not in search_dict:\n",
    "                        next_list.append(k)\n",
    "                        search_dict[k]+=1\n",
    "\n",
    "                # if j not in search_dict:\n",
    "                #     next_list=next_list+my_dict[j]\n",
    "                #     search_dict[j]+=1\n",
    "            now_list1=next_list.copy()\n",
    "        result=10**4\n",
    "        for i in roads:\n",
    "            if i[0] in search_dict or i[1] in search_dict:\n",
    "                result=min(result,i[2])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        res=inf\n",
    "        used=[False]*n\n",
    "        q=deque([1])\n",
    "        adjs=defaultdict(list)\n",
    "        for a,b,d in roads:\n",
    "            adjs[a].append((b,d))\n",
    "            adjs[b].append((a,d))\n",
    "        while q:\n",
    "            for nxt,d in adjs[q.popleft()]:\n",
    "                if d<res: res=d\n",
    "                if used[nxt-1]:continue\n",
    "                used[nxt-1]=True\n",
    "                q.append(nxt)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        parent = [i for i in range(n+1)]\n",
    "        rank = [1]*(n+1)\n",
    "        roads.sort(key=lambda x:x[2])\n",
    "        def fid(x):\n",
    "            if parent[x] == x:\n",
    "                return x\n",
    "            parent[x] = fid(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            root_x = fid(x)\n",
    "            root_y = fid(y)\n",
    "            if root_x != root_y:\n",
    "                if parent[root_x] > parent[root_y]:\n",
    "                    parent[root_y] = root_x\n",
    "                    rank[root_x] += rank[root_y]\n",
    "                else:\n",
    "                    parent[root_x] = root_y\n",
    "                    rank[root_y] += rank[root_x]\n",
    "        for x,y,p in roads:\n",
    "            union(x,y)\n",
    "        visited = defaultdict(set)\n",
    "        for i in range(1,n+1):\n",
    "            key = fid(i)\n",
    "            visited[key].add(i)\n",
    "        for x,y,p in roads:\n",
    "            if x in visited[key]:\n",
    "                return p\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        parent = [i for i in range(n+1)]\n",
    "        rank = [1]*(n+1)\n",
    "        roads.sort(key=lambda x:x[2])\n",
    "        def fid(x):\n",
    "            if parent[x] == x:\n",
    "                return x\n",
    "            parent[x] = fid(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            root_x = fid(x)\n",
    "            root_y = fid(y)\n",
    "            if root_x != root_y:\n",
    "                if parent[root_x] > parent[root_y]:\n",
    "                    parent[root_y] = root_x\n",
    "                    rank[root_x] += rank[root_y]\n",
    "                else:\n",
    "                    parent[root_x] = root_y\n",
    "                    rank[root_y] += rank[root_x]\n",
    "        for x,y,p in roads:\n",
    "            union(x,y)\n",
    "        visited = defaultdict(set)\n",
    "        nums = [inf]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            key = fid(i)\n",
    "            visited[key].add(i)\n",
    "        for x,y,p in roads:\n",
    "            if x in visited[key]:\n",
    "                return p\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        for x,y,z in roads:\n",
    "            g[x].append((y,z))\n",
    "            g[y].append((x,z))\n",
    "        \n",
    "        \n",
    "        def bfs(s):\n",
    "            ans = inf\n",
    "            q = deque([s])\n",
    "            vis = [False]*(n+1)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                vis[x] = True\n",
    "                for y,z in g[x]:\n",
    "                    ans = min(ans,z)\n",
    "                    if vis[y]:continue\n",
    "                    q.append(y)\n",
    "            return ans\n",
    "        return bfs(1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        d = {i: [] for i in range(n)}\n",
    "        for u, v, w in roads:\n",
    "            d[u-1].append(v-1)\n",
    "            d[v-1].append(u-1)\n",
    "        s, l = {0}, [0]\n",
    "        while l:\n",
    "            p = l.pop()\n",
    "            for i in d[p]:\n",
    "                if i not in s:\n",
    "                    s.add(i)\n",
    "                    l.append(i)\n",
    "        return min(i[2] for i in roads if i[0]-1 in s)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        neighbours = [[] for _ in range(n + 1)]\n",
    "        for u, v, w in roads:\n",
    "            neighbours[u].append((v, w))\n",
    "            neighbours[v].append((u, w))\n",
    "        res = 10000\n",
    "        seen = [False] * (n + 1)\n",
    "        seen[1] = True\n",
    "        a = [1]\n",
    "        i = 0\n",
    "        while i < len(a):\n",
    "            u = a[i]\n",
    "            i += 1\n",
    "            for v, w in neighbours[u]:\n",
    "                res = min(res, w)\n",
    "                if not seen[v]:\n",
    "                    seen[v] = True\n",
    "                    a.append(v)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        x = dict()\n",
    "        for i, j, k in roads:\n",
    "            if i in x:\n",
    "                x[i].append((j, k))\n",
    "            else:\n",
    "                x[i] = [(j, k)]\n",
    "            if j in x:\n",
    "                x[j].append((i, k))\n",
    "            else:\n",
    "                x[j] = [(i, k)]\n",
    "        vis = [False] * (n + 1)\n",
    "\n",
    "        ans = float('inf')\n",
    "        queue = deque([1])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            vis[node] = True\n",
    "            for i, k in x[node]:\n",
    "                if vis[i] == False:\n",
    "                    queue.append(i)\n",
    "                ans = min(ans, k)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for f, t, d in roads:\n",
    "            g[f].append((t, d))\n",
    "            g[t].append((f, d))\n",
    "\n",
    "        d = deque([1])\n",
    "        vis = set()\n",
    "        while d:\n",
    "            node = d.popleft()\n",
    "            if node in vis:\n",
    "                continue\n",
    "            vis.add(node)\n",
    "            for nxt, _ in g[node]:\n",
    "                d.append(nxt)\n",
    "            \n",
    "        ans = inf\n",
    "        for node in vis:\n",
    "            for _, d in g[node]:\n",
    "                ans = min(ans, d)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        map = defaultdict(list)\n",
    "        for a, b, dis in roads:\n",
    "            map[a].append((b, dis))\n",
    "            map[b].append((a, dis))\n",
    "        \n",
    "        ans = inf\n",
    "        not_visited = [True] * (n + 1)\n",
    "        # bfs，记录所有遇到过的城市\n",
    "        q = deque([1])\n",
    "        while q:\n",
    "            city = q.popleft()\n",
    "            for end, dis in map[city]:\n",
    "                if dis < ans:\n",
    "                    ans = dis\n",
    "                if not_visited[end]:\n",
    "                    not_visited[end] = False\n",
    "                    q.append(end)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        edges=defaultdict(list)\n",
    "        min_score=inf\n",
    "        for [a,b,d] in roads:\n",
    "            edges[a].append((b,d))\n",
    "            edges[b].append((a,d))\n",
    "            min_score=min(d,min_score)\n",
    "        h=[(1,inf)]\n",
    "\n",
    "        ans=inf\n",
    "        visited=[False]*(n+1)\n",
    "        while h:\n",
    "            u,d = h.pop()\n",
    "            # print(u,d,edges[u])\n",
    "            ans=min(ans,d)\n",
    "            visited[u]=True\n",
    "            for v,d in edges[u]:\n",
    "                if not visited[v]:\n",
    "                    h.append((v,d))\n",
    "                    if d==min_score:\n",
    "                        return min_score\n",
    "        # print(visited)\n",
    "        # print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # bfs+节点v集合+找最短距离边\n",
    "        maps = [[] for _ in range(n + 1)]\n",
    "        for s, e, d in roads:\n",
    "            maps[s].append([e, d])\n",
    "            maps[e].append([s, d])\n",
    "        q = [1]\n",
    "        v = set(q)\n",
    "        res = float(\"inf\")\n",
    "        for x in q:\n",
    "            for nex, d in maps[x]:\n",
    "                # 注意这里的更新不能放在if条件里面!!!\n",
    "                # 因为有可能nex节点已被遍历, 但x->nex的边尚未遍历过\n",
    "                res = min(res, d)\n",
    "                if nex not in v:\n",
    "                    v.add(nex)\n",
    "                    q.append(nex)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import deque\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # build graph\n",
    "        nodes = {}\n",
    "        edges = {}\n",
    "        for src, trg, dist in roads:\n",
    "            if src in nodes:\n",
    "                nodes[src].append(trg)\n",
    "            else:\n",
    "                nodes[src] = [trg]\n",
    "            if trg in nodes:\n",
    "                nodes[trg].append(src)\n",
    "            else:\n",
    "                nodes[trg] = [src]\n",
    "            \n",
    "            if src < trg:\n",
    "                edges[(src, trg)] = dist\n",
    "            else:\n",
    "                edges[(trg, src)] = dist\n",
    "\n",
    "        # BFS\n",
    "        visited = set()\n",
    "        tobeVisited = deque()\n",
    "        tobeVisited.append(1)\n",
    "        score = float('inf')\n",
    "        \n",
    "        while tobeVisited:\n",
    "            curNode = tobeVisited.popleft()\n",
    "            visited.add(curNode)\n",
    "\n",
    "            for neighbor in nodes[curNode]:\n",
    "                if neighbor in visited:\n",
    "                    continue\n",
    "                tobeVisited.append(neighbor)\n",
    "\n",
    "                src = curNode\n",
    "                trg = neighbor\n",
    "                if curNode > neighbor:\n",
    "                    src = neighbor\n",
    "                    trg = curNode\n",
    "                if edges[(src, trg)] < score:\n",
    "                    score = edges[(src, trg)]\n",
    "\n",
    "        return score\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dis = [{} for _ in range(n+1)]\n",
    "        for d in roads:\n",
    "            i, j, k = d\n",
    "            dis[i][j] = k\n",
    "            dis[j][i] = k\n",
    "        visited = set()\n",
    "        visited.add(1)\n",
    "        queue = deque()\n",
    "        queue.append(1)\n",
    "        res = inf\n",
    "        flag = False\n",
    "        while queue:\n",
    "            root = queue.popleft()\n",
    "            for k, v in dis[root].items():\n",
    "                res = min(res, v)\n",
    "                if k == n:\n",
    "                    flag = True\n",
    "                if k not in visited:\n",
    "                    visited.add(k)\n",
    "                    queue.append(k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        G = defaultdict(list)\n",
    "        for a,b,v in roads:\n",
    "            G[a].append([b,v])\n",
    "            G[b].append([a,v])\n",
    "        F = [0] * (n+1)\n",
    "        for i in range(1,n+1):\n",
    "            mn = inf\n",
    "            for _,j in G[i]:\n",
    "                mn = min(mn,j)\n",
    "            F[i] = mn\n",
    "        vis = [0] * (n+1)\n",
    "        vis[1] = 1\n",
    "        st = [1]\n",
    "        res = F[1]\n",
    "        while st:\n",
    "            for nxt,_ in G[st.pop()]:\n",
    "                if vis[nxt]:continue\n",
    "                vis[nxt] = 1\n",
    "                res = min(res,F[nxt])\n",
    "                st.append(nxt)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n+1)]\n",
    "        for r in roads:\n",
    "            a, b, d = r[0], r[1], r[2]\n",
    "            g[a].append((b, d))\n",
    "            g[b].append((a, d))\n",
    "        ans = inf\n",
    "        vis = [False] * (n+1)\n",
    "        def dfs(city):\n",
    "            nonlocal ans\n",
    "            vis[city] = True\n",
    "            for nxt, d in g[city]:\n",
    "                ans = min(ans, d)\n",
    "                if not vis[nxt]:\n",
    "                    dfs(nxt)\n",
    "\n",
    "        dfs(1)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        distance=defaultdict(list)\n",
    "        for l,r,d in roads:\n",
    "            distance[l].append((r,d))\n",
    "            distance[r].append((l,d))\n",
    "        query=[1]\n",
    "        ans=inf\n",
    "        visited={0}\n",
    "        while query:\n",
    "            q=query.pop()\n",
    "            for node,dis in distance[q]:\n",
    "                ans=min(ans,dis)\n",
    "                if node not in visited:\n",
    "                    visited.add(node)\n",
    "                    query.append(node)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for road in roads:\n",
    "            g[road[0]].append((road[1], road[2]))\n",
    "            g[road[1]].append((road[0], road[2]))\n",
    "        res = inf\n",
    "        vis = set()\n",
    "        def dfs(x):\n",
    "            vis.add(x)\n",
    "            for y, d in g[x]:\n",
    "                nonlocal res\n",
    "                res = min(res, d)\n",
    "                if y not in vis:\n",
    "                    dfs(y)\n",
    "        dfs(1)\n",
    "        dfs(n)                   \n",
    "        return res                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        vit = [False] * (n+1)\n",
    "\n",
    "        for a, b, d in roads:\n",
    "            g[a].append((b, d))\n",
    "            g[b].append((a, d))\n",
    "\n",
    "        ans = inf\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            vit[x] = True\n",
    "            for y, d in g[x]:\n",
    "                ans = min(d, ans)\n",
    "                if not vit[y]:\n",
    "                    dfs(y)\n",
    "        dfs(1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x,y,d in roads:\n",
    "            g[x-1].append((y-1, d))\n",
    "            g[y-1].append((x-1, d))\n",
    "        \n",
    "        ans = inf\n",
    "        vis = [False] * n\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            vis[x] = True\n",
    "            for y,d in g[x]:\n",
    "                ans = min(ans, d)\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        edges=defaultdict(list)\n",
    "        for [a,b,d] in roads:\n",
    "            edges[a].append((b,d))\n",
    "            edges[b].append((a,d))\n",
    "        h=[(1,inf)]\n",
    "        ans=inf\n",
    "        visited=[False]*(n+1)\n",
    "        while h:\n",
    "            u,d = h.pop()\n",
    "            # print(u,d,edges[u])\n",
    "            ans=min(ans,d)\n",
    "            visited[u]=True\n",
    "            for v,d in edges[u]:\n",
    "                if not visited[v]:\n",
    "                    h.append((v,d))\n",
    "        # print(visited)\n",
    "        # print(ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y, d in roads:\n",
    "            g[x - 1].append((y - 1, d))\n",
    "            g[y - 1].append((x - 1, d))\n",
    "        ans = inf\n",
    "        vis = [False] * n\n",
    "        def dfs(x: int) -> None:\n",
    "            nonlocal ans\n",
    "            vis[x] = True\n",
    "            for y, d in g[x]:\n",
    "                ans = min(ans, d)\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        map = defaultdict(dict)\n",
    "        for a, b, dis in roads:\n",
    "            map[a][b] = map[b][a] = dis\n",
    "        \n",
    "        ans = inf\n",
    "        visited = [False] * (n + 1)\n",
    "        # bfs，记录所有遇到过的城市\n",
    "        q = [1]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for city in tmp:\n",
    "                for end, dis in map[city].items():\n",
    "                    if dis < ans:\n",
    "                        ans = dis\n",
    "                    if not visited[end]:\n",
    "                        visited[end] = True\n",
    "                        q.append(end)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        \n",
    "        G=[[] for _ in range(n)]\n",
    "        for x, y,d in roads:\n",
    "           G[x-1]+=[[y-1,d]] \n",
    "           G[y-1]+=[[x-1,d]]\n",
    "        ans=inf\n",
    "        vis=[False]*n\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            vis[x]=True\n",
    "            for y,d in G[x]:\n",
    "                if d<ans:ans=d\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # 使用邻接表存储图\n",
    "        d = defaultdict(list)\n",
    "        for i in range(len(roads)):\n",
    "            u, v, w = roads[i]\n",
    "            d[u].append([v, w])\n",
    "            d[v].append([u, w])\n",
    "        \n",
    "        def bfs(d):\n",
    "            visited = defaultdict(bool)  # 每个点是否访问过了\n",
    "            start = 1\n",
    "            queue = deque([start])\n",
    "            visited[start] = True\n",
    "            res = 10 ** 9\n",
    "            while len(queue):\n",
    "                # 取队头\n",
    "                front = queue.popleft()\n",
    "                # 从这个开始进行邻接矩阵的遍历\n",
    "                for i in range(len(d[front])):\n",
    "                    end, cost = d[front][i]\n",
    "                    res = min(res, cost)\n",
    "                    if not visited[end]:\n",
    "                        visited[end] = True\n",
    "                        queue.append(end)\n",
    "            \n",
    "            return res\n",
    "\n",
    "        return bfs(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,y,d in roads:\n",
    "            g[x-1].append((y-1,d))\n",
    "            g[y-1].append((x-1,d))\n",
    "        print(g)\n",
    "        ans=inf\n",
    "        vis=[False]*n\n",
    "        def dfs(x):\n",
    "            nonlocal ans\n",
    "            vis[x]=True\n",
    "            for y,d in g[x]:\n",
    "                ans=min(ans,d)\n",
    "                if not vis[y]:\n",
    "                    dfs(y)\n",
    "        dfs(0)\n",
    "        return ans\n",
    "        # g=[[] for _ in range(n)]\n",
    "        # for x,y,d in roads:\n",
    "        #     g[x-1].append((y-1,d))\n",
    "        #     g[y-1].append((x-1,d))\n",
    "        # print(g)\n",
    "        # ans=inf\n",
    "        # vis=[False]*n\n",
    "        # res=inf\n",
    "        # path=[]\n",
    "        # def dfs(x):\n",
    "        #     nonlocal res\n",
    "        #     if x==n-1:\n",
    "        #         res=min(res,sum(path))\n",
    "        #     vis[x]=True\n",
    "        #     for y,d in g[x]:\n",
    "        #         if not vis[y]:\n",
    "        #             path.append(d)\n",
    "        #             dfs(y)\n",
    "        #             path.pop()\n",
    "        #             vis[y]=False\n",
    "\n",
    "        # dfs(0)\n",
    "        # print(path)\n",
    "        # print(res)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        edges = defaultdict(dict)\n",
    "        for f, t, d in roads:\n",
    "            edges[f][t] = d\n",
    "            edges[t][f] = d\n",
    "        ans = float(\"inf\")\n",
    "        # 求节点1所在的连通边\n",
    "        visited = [False] * (n + 1)\n",
    "        queue = deque([1])\n",
    "        visited[1] = True\n",
    "        while queue:\n",
    "            curNode = queue.popleft()\n",
    "            for nextNode, dist in edges[curNode].items():\n",
    "                ans = min(ans, dist)\n",
    "                if not visited[nextNode]:\n",
    "                    visited[nextNode] = True\n",
    "                    queue.append(nextNode)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a,b,d in roads:\n",
    "            g[a].append((b,d))\n",
    "            g[b].append((a,d))\n",
    "        \n",
    "        ans = inf\n",
    "        vis = set()\n",
    "        def dfs(u):\n",
    "            nonlocal ans\n",
    "            vis.add(u)\n",
    "            for v,d in g[u]:\n",
    "                ans = min(ans,d)\n",
    "                if v not in vis:\n",
    "                    dfs(v)\n",
    "\n",
    "        dfs(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        g = defaultdict(list)\n",
    "        for a,b,d in roads:\n",
    "            g[a].append((b,d))\n",
    "            g[b].append((a,d))\n",
    "        ans = inf\n",
    "        vis = set()\n",
    "        def dfs(u):\n",
    "            vis.add(u)\n",
    "            nonlocal ans\n",
    "            for v,d in g[u]:\n",
    "                ans = min(ans,d)\n",
    "                if v not in vis:\n",
    "                    dfs(v)\n",
    "        dfs(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v, d in roads:\n",
    "            graph[u].append([v, d])\n",
    "            graph[v].append([u, d])\n",
    "\n",
    "        self.res = float('inf')\n",
    "        visit = set()\n",
    "\n",
    "        def dfs(node):\n",
    "            # if not node:\n",
    "            #     return\n",
    "            if node in visit:\n",
    "                return\n",
    "            visit.add(node)\n",
    "            for nei, d in graph[node]:\n",
    "                # if nei not in visit:\n",
    "                #     visit.add(nei)\n",
    "                self.res = min(self.res, d)\n",
    "                dfs(nei)\n",
    "        dfs(1)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        q = deque([1])\n",
    "        vis = [False] * (n+1)\n",
    "        dis = {}\n",
    "        ans = inf\n",
    "        graph = [[] for _ in range(n+1)]\n",
    "        for fr, to, w in roads:\n",
    "            graph[fr].append(to)\n",
    "            graph[to].append(fr)\n",
    "            dis[(fr, to)] = dis[(to, fr)] = w\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            if vis[x]:\n",
    "                continue\n",
    "            vis[x] = True\n",
    "            for y in graph[x]:\n",
    "                ans = min(ans, dis[(x, y)])\n",
    "                q.append(y)\n",
    "        return ans;\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dp = [inf]*(n+1)\n",
    "        g = defaultdict(list)\n",
    "        for x,y,w in roads:\n",
    "            g[x].append((y,w))\n",
    "            g[y].append((x,w))\n",
    "        hq = []\n",
    "        heapq.heappush(hq,(inf,1))\n",
    "        while hq:\n",
    "            w,x = heapq.heappop(hq)\n",
    "            # print(w,x)\n",
    "            if w > dp[x]:\n",
    "                continue\n",
    "            # print(g[x])\n",
    "            for y,w2 in g[x]:\n",
    "                tmp = min(w,w2)\n",
    "                if tmp < dp[y]:\n",
    "                    dp[y] = tmp\n",
    "                    heapq.heappush(hq,(tmp,y))\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "                    \n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        dic = defaultdict(list)\n",
    "        for u,v,c in roads:\n",
    "            dic[u].append([v,c])\n",
    "            dic[v].append([u,c])\n",
    "        vis = set([])\n",
    "        res = float(\"inf\")\n",
    "        def dfs(node):\n",
    "            vis.add(node)\n",
    "            nonlocal res\n",
    "            for v,c in dic[node]:\n",
    "                res = min(res,c)\n",
    "                if v not in vis:\n",
    "                    dfs(v)\n",
    "                    \n",
    "        dfs(1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dis, r = dict(), defaultdict(list)\n",
    "        for a, b, d in roads:\n",
    "            r[a].append(b)\n",
    "            r[b].append(a)\n",
    "            dis[(a, b)] = d\n",
    "            dis[(b, a)] = d\n",
    "        m = inf\n",
    "        q = deque([1])\n",
    "        used = set((1, ))\n",
    "        while q:\n",
    "            x = q.popleft()\n",
    "            for y in r[x]:\n",
    "                if dis[(x, y)] < m:m = dis[(x, y)]\n",
    "                if y not in used:\n",
    "                    q.append(y)\n",
    "                    used.add(y)\n",
    "        return m\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dic={}\n",
    "        for a,b,c in roads:\n",
    "            if a not in dic:\n",
    "                dic[a]={}\n",
    "            if b not in dic:\n",
    "                dic[b]={}\n",
    "            if b not in dic[a]:\n",
    "                dic[a][b]=c\n",
    "            else:\n",
    "                dic[a][b]=min(c,dic[a][b])\n",
    "            if a not in dic[b]:\n",
    "                dic[b][a]=c\n",
    "            else:\n",
    "                dic[b][a]=miin(c,dic[b][a])\n",
    "        visit=[False]*(n+1)\n",
    "        self.mi=inf\n",
    "        def dfs(i):\n",
    "            visit[i]=True\n",
    "            for j in dic[i]:\n",
    "                self.mi=min(self.mi,dic[i][j])\n",
    "                if not visit[j]:\n",
    "                    dfs(j)\n",
    "        dfs(1)\n",
    "        return self.mi\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        mindist = 1e9\n",
    "        for u, v, w in roads:\n",
    "            graph[u].append((v, w))\n",
    "            graph[v].append((u, w))\n",
    "            mindist = min(mindist, w)\n",
    "        \n",
    "        visited = [float('inf')] * (n + 1)\n",
    "        heap = [(1e9, 1)]\n",
    "        ans = float('inf')\n",
    "        while heap:\n",
    "            dist, node = heapq.heappop(heap)\n",
    "            if node == n:\n",
    "                ans = min(ans, dist)\n",
    "                if ans == mindist:\n",
    "                    return ans\n",
    "            if visited[node] <= dist:\n",
    "                continue\n",
    "            visited[node] = dist\n",
    "            for u, w in graph[node]:\n",
    "                if min(dist, w) >= visited[u]:\n",
    "                    continue\n",
    "                heapq.heappush(heap, [min(dist, w), u])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ans = float(\"inf\")\n",
    "        distance = [set() for i in range(n)]\n",
    "        for i, j, k in roads:\n",
    "            distance[i-1].add((j, k))\n",
    "            distance[j-1].add((i, k))\n",
    "        s = deque(distance[0])\n",
    "        visited = [0] * n\n",
    "        while s:\n",
    "            # print(s)\n",
    "            city, d = s.popleft()\n",
    "            ans = min(ans, d)\n",
    "            if not visited[city-1]:\n",
    "                for x in distance[city-1]:\n",
    "                    s.append(x)\n",
    "            visited[city-1] = 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(dict)\n",
    "        for i, j, v in roads:\n",
    "            cnt[i][j] = v\n",
    "            cnt[j][i] = v\n",
    "        d = Counter()\n",
    "        for i in cnt:\n",
    "            d[i] = min(cnt[i].values())\n",
    "        cur = [1]\n",
    "        meet = {1}\n",
    "        res = inf\n",
    "        while cur:\n",
    "            i = cur.pop()\n",
    "            res = min(res, d[i])\n",
    "            for j in cnt[i]:\n",
    "                if j not in meet:\n",
    "                    meet.add(j)\n",
    "                    cur.append(j)\n",
    "        return res\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph=defaultdict(dict)\n",
    "        for a,b,c in roads:\n",
    "            graph[a][b]=c\n",
    "            graph[b][a]=c\n",
    "        ret=float('inf')\n",
    "        def dfs(root,vis):\n",
    "            nonlocal ret\n",
    "            d=graph[root]\n",
    "            for nei in d:\n",
    "                ret=min(ret,d[nei])\n",
    "                if nei not in vis:\n",
    "                    vis.add(nei)\n",
    "                    dfs(nei,vis)\n",
    "        vis=set()\n",
    "        vis.add(1)\n",
    "        dfs(1,vis)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        min_score = 10**5\n",
    "        # print([i for i in range(n)])\n",
    "        model = UnionFindSet([i for i in range(n)])\n",
    "        \n",
    "        road_rec = defaultdict(list)\n",
    "        \n",
    "        for road in roads:\n",
    "            model.union(road[0]-1, road[1]-1)\n",
    "            road_rec[road[0]-1].append(road[2])\n",
    "            road_rec[road[1]-1].append(road[2])\n",
    "            \n",
    "        father = [-1]*n\n",
    "        for i in range(n):\n",
    "            father[i] = model.find(i)\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            if father[i]!=father[0]:\n",
    "                continue\n",
    "            node_list = road_rec[i]\n",
    "            min_score = min(min_score, min(node_list))\n",
    "        return min_score\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "import numpy as np\n",
    " \n",
    "class UnionFindSet():\n",
    "    def __init__(self, data_list):\n",
    "        # 初始化两个字典，分别保存节点的父节点（并查集）和保存父节点的大小\n",
    "        self.father_dict = {}  # father_dict[i]表示节点i的父节点\n",
    "        self.size_dict = {}  # size_dict[i]表示节点i的后代节点个数\n",
    "        # 初始化节点，将节点的父节点设为自身，size设为1\n",
    "        for node in data_list:\n",
    "            self.father_dict[node] = node\n",
    "            self.size_dict[node] = 1\n",
    " \n",
    "    # 递归查找根节点（父节点是自己的节点）\n",
    "    def find(self, node):\n",
    "        # 获取节点的父节点\n",
    "        father = self.father_dict[node]\n",
    "        # 查找当前节点的父节点，直到父节点是其自己\n",
    "        if(node != father):\n",
    "            # 在降低树高优化时，确保父节点大小字典正确\n",
    "            if father != self.father_dict[father]:\n",
    "                self.size_dict[father] -= 1\n",
    "            # 递归查找节点的父节点，直到根节点\n",
    "            father = self.find(father)\n",
    "        # 在查找父节点的时候，顺便把当前节点移动到父节点上面（优化操作）\n",
    "        self.father_dict[node] = father\n",
    "        return father\n",
    " \n",
    "    # 查看两个节点是不是在一个集合里面\n",
    "    def is_same_set(self, node_a, node_b):\n",
    "        # 获取两个节点的父节点并比较父节点是否是同一个\n",
    "        return self.find(node_a) == self.find(node_b)\n",
    " \n",
    "    # 将两个集合合并在一起（只需合并根节点），size_dict大吃小（尽可能降低树高）\n",
    "    def union(self, node_a, node_b):\n",
    "        if node_a is None or node_b is None:\n",
    "            return\n",
    "        # 找到两个节点各自的根节点\n",
    "        a_root = self.find(node_a)\n",
    "        b_root = self.find(node_b)\n",
    " \n",
    "        # 两个节点不在同一集合中，则合并两个集合\n",
    "        if(a_root != b_root):\n",
    "            # 获取两个集合根节点的大小\n",
    "            a_set_size = self.size_dict[a_root]\n",
    "            b_set_size = self.size_dict[b_root]\n",
    "            # 判断两个集合根节点大小，并进行合并（大吃小）\n",
    "            if(a_set_size >= b_set_size):\n",
    "                # 合并集合\n",
    "                self.father_dict[b_root] = a_root\n",
    "                # 更新大小\n",
    "                self.size_dict[a_root] = a_set_size + b_set_size\n",
    "            else:\n",
    "                # 合并集合\n",
    "                self.father_dict[a_root] = b_root\n",
    "                # 更新大小\n",
    "                self.size_dict[b_root] = a_set_size + b_set_size\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        grid = defaultdict(set)\n",
    "        for u, v, w in roads:\n",
    "            grid[u].add((v, w))\n",
    "            grid[v].add((u, w))\n",
    "        \n",
    "        from collections import deque\n",
    "        q = deque([1])\n",
    "        vis = {1}\n",
    "        res = float('inf')\n",
    "        while q:\n",
    "            u = q.popleft()\n",
    "            for v, w in grid[u]:\n",
    "                res = min(res, w) \n",
    "                if v in vis:\n",
    "                    continue\n",
    "                vis.add(v)\n",
    "                q.append(v)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        ans = float(\"inf\")\n",
    "        distance = [set() for i in range(n)]\n",
    "        for i, j, k in roads:\n",
    "            distance[i-1].add((j, k))\n",
    "            distance[j-1].add((i, k))\n",
    "        visited = [0] * n\n",
    "        def dfs(x: int):\n",
    "            nonlocal ans\n",
    "            visited[x] = 1\n",
    "            for y, k in distance[x]:\n",
    "                ans = min(ans, k)\n",
    "                if not visited[y-1]:\n",
    "                    dfs(y-1)\n",
    "            \n",
    "        dfs(0)   \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        gt = [[] for _ in range(n + 1)]\n",
    "        for road in roads:\n",
    "            [s, e, c] = road\n",
    "            gt[s].append([e, c])\n",
    "            gt[e].append([s, c])\n",
    "            \n",
    "        # print(gt)\n",
    "        \n",
    "        min_score = inf\n",
    "        vis = set()\n",
    "        q = [1]\n",
    "        while q:\n",
    "            tq = []\n",
    "            while q:\n",
    "                target = q.pop()\n",
    "                for [next, c] in gt[target]:\n",
    "                    if (target, next) not in vis:\n",
    "                        vis.add((target, next))\n",
    "                        vis.add((next, target))\n",
    "                        tq.append(next)\n",
    "                        min_score = min(min_score, c)\n",
    "            q = tq\n",
    "            \n",
    "        # print(vis)\n",
    "        return min_score\n",
    "        \n",
    "            \n",
    "            \n",
    "                \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        INF = 9999999\n",
    "        graph = {i: dict() for i in range(1, n + 1)}\n",
    "        for a, b, distance in roads:\n",
    "            graph[a][b] = distance\n",
    "            graph[b][a] = distance\n",
    "        print(graph)\n",
    "        connected = {1}\n",
    "        pivots = [1]\n",
    "        while pivots:\n",
    "            node = pivots.pop()\n",
    "            for child in graph[node]:\n",
    "                if child not in connected:\n",
    "                    connected.add(child)\n",
    "                    pivots.append(child)\n",
    "        \n",
    "        minimum = None\n",
    "        for node in connected:\n",
    "            val = min(graph[node].values())\n",
    "            if minimum is None or val < minimum:\n",
    "                minimum = val\n",
    "        return minimum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for u, v, dist in roads:\n",
    "            graph[u].append((v, dist))\n",
    "            graph[v].append((u, dist))\n",
    "        \n",
    "        visited = set()\n",
    "        res = float('inf')\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(node):\n",
    "            nonlocal res\n",
    "            visited.add(node)\n",
    "            for neigh, dist in graph[node]:\n",
    "                res = min(res, dist)\n",
    "                if neigh not in visited:\n",
    "                    dfs(neigh)\n",
    "        \n",
    "        dfs(1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "\n",
    "        g = defaultdict(dict)\n",
    "        for a, b, d in roads:\n",
    "            g[a][b] = d\n",
    "            g[b][a] = d\n",
    "        \n",
    "        vis = {1}\n",
    "\n",
    "        def dfs(node):\n",
    "            for nei, _ in g[node].items():\n",
    "                if nei not in vis:\n",
    "                    vis.add(nei)\n",
    "                    dfs(nei)\n",
    "        dfs(1)\n",
    "        ans = float('inf')\n",
    "        for node in vis:\n",
    "            for k, v in g[node].items():\n",
    "                ans = min(ans, v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dict = defaultdict(list) # 映射\n",
    "        dict2= defaultdict(int) # 距离\n",
    "        _set=set()\n",
    "        _set.add(1)\n",
    "      \n",
    "        res=99999\n",
    "        for a,b,c in roads: \n",
    "            dict[a].append(b) \n",
    "            dict[b].append(a) \n",
    "            dict2['{}-{}'.format(a,b)]=c\n",
    "        # print(dict)\n",
    "        # print(dict2)\n",
    "        \n",
    "        \n",
    "        def main(arr): \n",
    "            for i in arr:\n",
    "                if i not in _set:\n",
    "                    _set.add(i)\n",
    "                    main(dict[i])\n",
    "        main(dict[1])\n",
    "        \n",
    "        # print(_set)\n",
    "        for i in range(1,n+1): \n",
    "            if i not in _set:\n",
    "                continue\n",
    "            arr=dict[i]\n",
    "            for j in arr: \n",
    "                if dict2['{}-{}'.format(i,j)]>0:\n",
    "                    res=min(res,dict2['{}-{}'.format(i,j)]) \n",
    "                elif dict2['{}-{}'.format(j,i)]>0:\n",
    "                    res=min(res,dict2['{}-{}'.format(j,i)])\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        maps = [[] for _ in range(n+1)]\n",
    "        for s, e, d in roads:\n",
    "            maps[s].append([e, d])\n",
    "            maps[e].append([s, d])\n",
    "        v = set()\n",
    "        q = [1]\n",
    "        res = float(\"inf\")\n",
    "        for x in q:\n",
    "            for nex, d in maps[x]:\n",
    "                if (x, nex) not in v:\n",
    "                    res = min(res, d)\n",
    "                    v.add((x, nex))\n",
    "                    v.add((nex, x))\n",
    "                    q.append(nex)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        dct = [dict() for _ in range(n + 1)]\n",
    "        for i, j, c in roads:\n",
    "            dct[i][j] = c\n",
    "            dct[j][i] = c\n",
    "        # Dijkstra\n",
    "        visit = [float(\"inf\")] * (n + 1)\n",
    "        stack = [[dct[1][j], 1] for j in dct[1]]\n",
    "        while stack:\n",
    "            dis, i = heapq.heappop(stack)\n",
    "            if visit[i] <= dis:\n",
    "                # 已经搜寻过更短的距离则跳过\n",
    "                continue\n",
    "            visit[i] = dis\n",
    "            for j in dct[i]:\n",
    "                heapq.heappush(stack, [min(dis, dct[i][j]), j])\n",
    "        return visit[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        \"\"\" g = [[] for _ in range(n)]\n",
    "        for u,v,w in roads:\n",
    "            g[(u,v)] = w \"\"\"\n",
    "        dct = defaultdict(dict)\n",
    "        for u,v,w in roads:\n",
    "            dct[u][v] = w\n",
    "            dct[v][u] = w\n",
    "        visited = set()\n",
    "        ans = inf\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            visited.add(i)\n",
    "            for j in dct[i]:\n",
    "                ans = min(ans,dct[i][j])\n",
    "                if j not in visited:\n",
    "                    dfs(j)\n",
    "        dfs(1)\n",
    "        return ans\n",
    "    \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        scores = defaultdict(list)\n",
    "        connects = defaultdict(set)\n",
    "        for s, e, score in roads:\n",
    "            connects[s].add(e)\n",
    "            connects[e].add(s)\n",
    "            scores[s].append(score)\n",
    "            scores[e].append(score)\n",
    "        cur = connects[n]\n",
    "        visited = {n}\n",
    "        \n",
    "        min_score = inf\n",
    "        while cur:\n",
    "            new_cur = set()\n",
    "            for c in cur:\n",
    "                new_cur |= connects[c] - visited\n",
    "                visited |= new_cur\n",
    "            cur = new_cur\n",
    "        min_score = min(min_score, min([min(scores[i]) for i in visited]))\n",
    "        return min_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def dfs(node):\n",
    "            nonlocal seen, ans\n",
    "            if node in seen:\n",
    "                return\n",
    "            seen.add(node)\n",
    "            for child in hashmap[node]:\n",
    "                ans = min(ans, distance[(child, node)])\n",
    "                dfs(child)\n",
    "            \n",
    "        seen = set()\n",
    "        ans = 10000\n",
    "        hashmap = collections.defaultdict(list)\n",
    "        distance = {}\n",
    "        for a, b, c in roads:\n",
    "            hashmap[a].append(b)\n",
    "            hashmap[b].append(a)\n",
    "            distance[(a, b)] = c\n",
    "            distance[(b, a)] = c\n",
    "        dfs(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        seen = set()\n",
    "        q = []\n",
    "        result = 10**4\n",
    "        mmap = {}\n",
    "        for i in range(len(roads)):\n",
    "            a, b, d = roads[i]\n",
    "            if a not in mmap:\n",
    "                mmap[a] = {}\n",
    "            mmap[a][b] = d\n",
    "            if b not in mmap:\n",
    "                mmap[b] = {}\n",
    "            mmap[b][a] = d\n",
    "            if a == 1:\n",
    "                q.append(b)\n",
    "                seen.add((a, b))\n",
    "                result = min(result, d)\n",
    "            if b == 1:\n",
    "                q.append(a)\n",
    "                seen.add((a, b))\n",
    "                result = min(result, d)\n",
    "        while q:\n",
    "            a = q.pop()\n",
    "            for b, d in mmap[a].items():\n",
    "                if (a, b) not in seen:\n",
    "                    result = min(result, d)\n",
    "                    q.append(b)\n",
    "                    seen.add((a, b))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        road_dict = defaultdict(list)\n",
    "        for x,y,dist in roads:\n",
    "            road_dict[x].append((y,dist))\n",
    "            road_dict[y].append((x,dist))\n",
    "        seen = set()\n",
    "        ans = float('inf')\n",
    "        visited = [0] * (n+1)\n",
    "        def dfs(cur):\n",
    "            nonlocal ans, visited\n",
    "            visited[cur] = 1\n",
    "            for c,d in road_dict[cur]:\n",
    "                if((cur, c, d) in seen):\n",
    "                    continue\n",
    "                seen.add((cur, c, d))\n",
    "                seen.add((c, cur, d))\n",
    "                ans = min(d, ans)\n",
    "                if(not visited[c]):\n",
    "                    dfs(c)\n",
    "        dfs(1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "\n",
    "        g2 = collections.defaultdict(list)\n",
    "        g = dict()\n",
    "        for s,e, w in roads:\n",
    "            g2[s].append(e)\n",
    "            g2[e].append(s)\n",
    "            g[(s,e)] = w\n",
    "            g[(e,s)] = w\n",
    "        \n",
    "        def dfs(s):\n",
    "            for e in g2[s]:\n",
    "                self.ans = min(self.ans, g[(s,e)])\n",
    "                if e not in vis:\n",
    "                    vis.add(e)\n",
    "                    dfs(e)\n",
    "\n",
    "        self.ans = 1e9\n",
    "        vis = set()\n",
    "        dfs(1)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def minScore(self, n: int, roads: List[List[int]]) -> int:\n",
    "        # 首先本题是一个无向图，很可能存在环，可以来回往复多次，dfs时必须要构建数据结构来记录哪些点已经遍历过\n",
    "        # 本题是求 \"这条路径中道路的 最小 距离\"，所以只要我在1号和n号所共同存在的连通块中找到一条最短的边即可(因为我人为地总有办法找到一条包含该最短边的路径，哪怕绕远路也要通过这条最短路)\n",
    "        # 由于测试数据保证1和n之间至少存在一条路径，也即保证1和n必定在同一个连通块内，那么我们直接从1号点开始做 dfs 或 bfs 遍历整个连通块即可\n",
    "        graph = defaultdict(int)\n",
    "        neighbors = defaultdict(list)\n",
    "        st = [0]*(n+10)\n",
    "        ans = 0x3f3f3f3f\n",
    "\n",
    "        def add(a, b, w):\n",
    "            graph[(a,b)] = w\n",
    "            graph[(b,a)] = w\n",
    "            neighbors[a].append(b)\n",
    "            neighbors[b].append(a)\n",
    "        \n",
    "        def dfs(cur_node, res)->bool:\n",
    "            for neighbor in neighbors[cur_node]:\n",
    "                if 1-st[neighbor]:  # neighbor 还没被搜到\n",
    "                    st[neighbor]=1\n",
    "                    res = min(res, dfs(neighbor, res))\n",
    "                # neighbor 之前已经被搜到了\n",
    "                res = min(res, graph[(cur_node,neighbor)])\n",
    "            return res\n",
    "        # 构图\n",
    "        for a, b, w in roads:\n",
    "            add(a,b,w)\n",
    "            add(b,a,w)\n",
    "        # 遍历连通块\n",
    "        return dfs(1, ans)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
